package a2;

import java.util.ArrayList;
import java.util.List;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;

public class FloydWarshal implements Algorithm{

	int counter = 0;
	
	@Override//überbleibsel einer älteren implementierung
	public List<String> getShortestWay(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph, String source, String target) {
		return runFloydWarshal(graph, source, target).way;
	}

	@Override
	public int getLastAccessCount() {
		return counter;
	}
	
	//Die eigentliche Implementierung des Algorithmus
	private Result runFloydWarshal(SimpleDirectedWeightedGraph<String, DefaultWeightedEdge> graph, String source, String target) {
		counter = 0;
		Result result = new Result();
		if (!graph.containsVertex(source) || !graph.containsVertex(target)) {//wenn ziel oder start nicht im graphen sind
			result.way = null;
			return result;
		}
		ArrayList<String> vertices = new ArrayList<String>(graph.vertexSet()); //Ecken in eine ArrayListe kopieren, um die Reihenfolge unter allen Umständen beizubehalten
		int[][] transitMatrix = new int[vertices.size()][vertices.size()];//eine matrix mit städteanzahl x städteanzahl
		double[][] distanzMatrix = new double[vertices.size()][vertices.size()];//-"-

		for (int i = 0; i < vertices.size(); ++i) {//distanzmatrix und transitmatrix wird gebaut
			for(int j = 0; j < vertices.size(); ++j) {//iteration über die matrix
				transitMatrix[i][j] = -1; //Hier muss die transitMatrix mit -1 initialisiert werden, da 0 ein gültiger Index ist
				if (graph.containsEdge(vertices.get(i), vertices.get(j)))//alle kombinationen von kanten
					distanzMatrix[i][j] = graph.getEdgeWeight(graph.getEdge(vertices.get(i), vertices.get(j)));//setzt die gewichtung der kante an der position [i][j] in der distanzmatrix
				else if (i == j)
					distanzMatrix[i][j] = 0;//a->a || b->b ...
				else 
					distanzMatrix[i][j] = Double.POSITIVE_INFINITY;//kante existiert nicht
			}
		}
		
		for (int j = 0; j < vertices.size(); ++j) {
			for (int i = 0; i < vertices.size(); ++i) {
				if (i != j) {//nur für ecken, die nicht sie selber sind
					for(int k = 0; k < vertices.size(); ++k) {
						if (k != j) {
							if (distanzMatrix[i][j] + distanzMatrix[j][k] < distanzMatrix[i][k]) {//direkte weg ist länger als umweg über j
								distanzMatrix[i][k] = distanzMatrix[i][j] + distanzMatrix[j][k];//kürzeren weg eintragen
								transitMatrix[i][k] = j;
								counter += 2; //Schreiben in Transitmatrix und schreiben in distanzmatrix
							}
							counter += 3; //d[i][j], d[j][k], d[i][k] auslesen
						}
					}
				}
			}
		}
		
		int sourceIndex = vertices.indexOf(source);
		int targetIndex = vertices.indexOf(target);
		if (distanzMatrix[sourceIndex][targetIndex] == Double.POSITIVE_INFINITY)
			return result; //Leere Liste zurückgeben, wenn es keine Verbindung von source nach target gibt
		ArrayList<Integer> indexWay = findWay(transitMatrix, sourceIndex, targetIndex); //Weg rekursiv als Liste der indizies holen
		for(Integer i : indexWay) { //Indexliste in Stringliste umrechnen
			result.way.add(vertices.get(i));
		}
		if (result.way.size() == 2 && result.way.get(0).equals(result.way.get(1)))  //Wenn Start == Ziel, dann nicht doppelt erwähnen
			result.way.remove(1);
				
		return result;
	}

	private class Result {
		ArrayList<String> way = new ArrayList<String>();  
	}
	
	private ArrayList<Integer> findWay(int[][] transitMatrix, int source, int target) {
		ArrayList<Integer> al = new ArrayList<Integer>();
		if (transitMatrix[source][target] == -1) {//direktverbindung vorhanden
			al.add(source);
			al.add(target);
		} else {//falls nicht
			al.addAll(findWay(transitMatrix, source, transitMatrix[source][target]));//rekursive wegsuche, für den fall das zwischenwege vorhanden sind
			al.remove(al.size()-1); //Das letzte Element muss entfernt werden, da es in beiden Listen vorkommt und ansonsten doppelt wäre
			al.addAll(findWay(transitMatrix, transitMatrix[source][target], target));
		}		
		return al;
	}
}
